/**
* @version:1.0
* @author kevinnan.org.cn  2018212114@mail.hfut.edu.cn
* @date 2020/7/16
* @Content:常用排序头文件定义
*/

#ifndef MY_ALGRITHM_SORT_H_
#define MY_ALGRITHM_SORT_H_

#include <iostream>
#include <vector>
#include <algorithm>
//c++11引入的新的计时方法
#include <chrono>   
//C语言标准库
#include "stdlib.h"
#include "time.h"

using namespace std;
using namespace chrono;


/**
  * 排序算法类
  */
class Sort{
private:
	// 需要进行排序的数组
	std::vector<int> array;


public:
	Sort();


	//　打印数组内容
	void DisplayArray(const std::vector<int>& v);


	/**　
	　　* 冒泡排序算法
	  * 依次比较数组中相邻的元素，如果前者比后者大，则交换值．
	  * 上述步骤重复size()次，即可使数组所有元素有序
	  */
	void BubbleSort();


	/**
	  * 优化版本的冒泡排序算法
	  * 传统的冒泡排序算法有点笨,比如当一次排序过程中相邻的元素都没有发生交换，
	  	这说明此时数组已经是有序的了，我们无需再进行比较了．
	  	因此，只需要在代码中加入一个bool型的状态变量来判断是否有元素的交换，
	  	如果没有，则排序结束．
	  */ 
	void OptimizeBubbleSort();	


	/** 
	  * 插入排序算法
	  * 从数组左边第二个元素开始，依次向左和其左边的元素比较，
	  * 如果遇到比它大的元素，则继续向左，直到遇到比它小的元素则放在该元素右边
	  */
	void InsertSort();


	/**　
	  * 希尔排序算法
	  * 希尔排序是插入排序的一种变种，它是通过交换不相邻的元素来实现对数组的局部进行排序，
	  * 先让数组中任意间隔为h的元素有序(使用直接插入排序)，然后让h一直缩小，当h=1时，全部元素有序．
	  * 刚开始h=n/2，接着h=n/4，直至h=1．
	  */
	void ShellSort();


	/**
	  * 归并排序算法
	  * 分-->治-->合
	  * 分开操作
	  */
	void mergeSort(std::vector<int>& Array, int low, int height);


	/**
	  *合并操作
	  */
	void Merge(std::vector<int>& Array, int low, int height);


	/**
	  *归并排序主函数
	  */
	void MergeSort();


	/**
	  *快速排序分割函数
	  */
	int Partition(std::vector<int>& Array, int low, int height);


	/**
	  *快速排序算法
	  */
	void QSort(std::vector<int>& Array, int low, int height);


	void QuickSort();


	void HSort(std::vector<int>& Array);

	/**
	  * 调整堆
	  */
	void adjustHeap(std::vector<int>& Array, int length);


	/**
	  *　堆排序
	  */
	void HeapSort();




};

#endif